package com.atwulidun.sort;

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void selectSort(int[] arr) {
        // 外层循环控制轮数
        for (int i = 0; i < arr.length - 1; i++) {
            // 首先假定每一轮最小的数为进行该轮比较的第一个数
            // 并且最小下表为该轮第一个数的下标
            int min = arr[i];
            int minIndex = i;
            // 内层循环控制每一轮的比较
            // 注意从每一轮的第二个数开始(j = i + 1)
            // 特别注意：j < arr.length - 1 - i是不对的，因为前面j = i + 1已经在缩小范围了，
            // 这里应该为j < arr.length，保证数组的最后一个数也能参与比较
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 本轮比较结束之后，将的到的最小的值和本轮进行比较的第一个数进行交换
            // 优化：若本轮比较得到的最小的数就位参与本轮比较的第一个数，则不需要交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];// 原先最小值处变为参与比较的第一个数的值
                arr[i] = min;// 参与比较的第一个数的值变为最小值
            }
            System.out.println("第" + (i + 1) + "轮排序：");
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("全部排序完后为：");
        System.out.println(Arrays.toString(arr));
    }
}
